package dp;

import java.util.LinkedList;

/**
 * 用动态规划解决背包问题
 *
 * 把O(2^n)时间复杂度降为O(n^2)
 */
public class PackSolution {

    /**
     * 旅行物品
     */
    public static class TravelGoods {
        /**
         * 名字
         */
        private String name;

        /**
         * 重量
         */
        private int weight;

        /**
         * 价值
         */
        private int value;

        public TravelGoods(String name, int weight, int value) {
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return name;
        }
    }

    /**
     * 背包
     */
    public static class Pack {
        /**
         * 所装物品
         */
        private LinkedList<TravelGoods> goodsList = new LinkedList<>();

        /**
         * 总价值
         */
        private int totalValue = 0;

        public Pack() {

        }

        public Pack(TravelGoods goods) {
            goodsList.add(goods);
            totalValue += goods.value;
        }

        @Override
        public String toString() {
            return "Pack{" +
                    "totalValue=" + totalValue +
                    ", goodsList=" + goodsList +
                    '}';
        }
    }

    public static void main(String[] args) {

        TravelGoods water = new TravelGoods("水", 3, 10);
        TravelGoods book = new TravelGoods("书", 1, 3);
        TravelGoods food = new TravelGoods("食物", 2, 9);
        TravelGoods jack = new TravelGoods("夹克", 2, 5);
        TravelGoods camera = new TravelGoods("相机", 1, 6);

        LinkedList<TravelGoods> goods = new LinkedList<>();
        goods.add(water);
        goods.add(book);
        goods.add(food);
        goods.add(jack);
        goods.add(camera);

        Pack[][] valueDp = new Pack[][]{
                {new Pack(), new Pack(), new Pack(water), new Pack(water), new Pack(water), new Pack(water)},
                {new Pack(book), new Pack(), new Pack(), new Pack(), new Pack(), new Pack()},
                {new Pack(book), new Pack(), new Pack(), new Pack(), new Pack(), new Pack()},
                {new Pack(book), new Pack(), new Pack(), new Pack(), new Pack(), new Pack()},
                {new Pack(camera), new Pack(), new Pack(), new Pack(), new Pack(), new Pack()},
        };

        for (int row = 1; row < valueDp.length; row++) {
            for (int col = 1; col < valueDp[0].length; col++) {
                TravelGoods travelGoods = goods.get(row);
                Pack abovePack = valueDp[row - 1][col];

                boolean filled = false;
                //尝试把自己放进入并且有剩余空间，加上以前这个剩余空间最大可以放多少
                if (col + 1 > travelGoods.weight) {
                    Pack otherPack = valueDp[row - 1][col - travelGoods.weight];
                    int curValue = travelGoods.value + otherPack.totalValue;
                    if (abovePack.totalValue < curValue) {
                        valueDp[row][col].goodsList.clear();
                        valueDp[row][col].goodsList.addAll(otherPack.goodsList);
                        valueDp[row][col].goodsList.add(travelGoods);
                        valueDp[row][col].totalValue = curValue;
                        filled = true;
                    }
                } else if (col + 1 == travelGoods.weight) {
                    //刚刚够装自己
                    int curValue = travelGoods.value;
                    if (abovePack.totalValue < curValue) {
                        valueDp[row][col].goodsList.clear();
                        valueDp[row][col].goodsList.add(travelGoods);
                        valueDp[row][col].totalValue = curValue;
                        filled = true;
                    }
                }
                if (!filled) {
                    valueDp[row][col].goodsList.clear();
                    valueDp[row][col].goodsList.addAll(abovePack.goodsList);
                    valueDp[row][col].totalValue = abovePack.totalValue;
                }
            }
        }

        System.out.println("max value:" + valueDp[4][5]);
    }
}
